package com.itheima.leetcode.od.b.string;

import java.util.Arrays;
import java.util.HashSet;

/**
 * (B卷,200分)- 数字游戏（Java & JS & Python）
 * <p>
 * 题目描述
 * <p>
 * 小明玩一个游戏。
 * <p>
 * 系统发1+n张牌，每张牌上有一个整数。
 * <p>
 * 第一张给小明，后n张按照发牌顺序排成连续的一行。
 * <p>
 * 需要小明判断，后n张牌中，是否存在连续的若干张牌，其和可以整除小明手中牌上的数字。
 * <p>
 * 输入描述
 * <p>
 * 输入数据有多组，每组输入数据有两行，输入到文件结尾结束。
 * <p>
 * 第一行有两个整数n和m，空格隔开。m代表发给小明牌上的数字。
 * <p>
 * 第二行有n个数，代表后续发的n张牌上的数字，以空格隔开。
 * <p>
 * 输出描述
 * <p>
 * 对每组输入，如果存在满足条件的连续若干张牌，则输出1;否则，输出0
 * <p>
 * 备注
 * 1 ≤ n ≤ 1000
 * 1 ≤ 牌上的整数 ≤ 400000
 * 输入的组数，不多于1000
 * 用例确保输入都正确，不需要考虑非法情况。
 * <p>
 * 用例
 * <p>
 * 输入	6 7
 * 2 12 6 3 5 5
 * 10 11
 * 1 1 1 1 1 1 1 1 1 1
 * 输出
 * 1
 * <p>
 * 0
 * <p>
 * 说明	两组输入。第一组小明牌的数字为7，再发了6张牌。第1、2两张牌教字和为14，可以整除7，输出1，第二组小明牌的教字为11，再发了10张牌，这10张牌数字和为10，无法整除11，输出0。
 * <p>
 * 题目解析
 * <p>
 * 本题考察前缀和知识，以及数学问题。
 * <p>
 * 本题要求连续若干张牌的和，其实就是求区间的元素之和。
 * <p>
 * 而求解任意区间和的最佳算法就是：前缀和之差，这个知识点可以看下
 * <p>
 * 算法设计 - 前缀和 & 差分数列_伏城之外的博客-CSDN博客
 * <p>
 * 利用前缀和，我们可以在O(1)的时间求解出[L,R]区间和 = preSum[R] - preSum[L-1]。
 * <p>
 * 那么接下来，我们是否需要双重for遍历出所有区间，然后逐一验证对应区间和是否可以整除k呢？
 * <p>
 * 本题中每组用例最多n = 1000张牌，因此双重for遍历对应牌的所有连续区间的时间复杂度O(n^2)。
 * <p>
 * 而本题有最多有1000组用例，因此相当于O(n^3)的时间复杂度，这是非常容易超时的。
 * <p>
 * 本题优化是基于一个数学性质：
 * <p>
 * 如果两个数a,b，他们的差a - b可以被k整除，则必然 a % k == b % k。
 * <p>
 * 反之，如果a % k == b % k，那么 a - b 必然可以被k整除。
 * <p>
 * 大家可以自行验证下这个数学性质。
 * <p>
 * 验证好后，我们只需要将preSum[R]带入a，preSum[L-1]带入b 再来看看：
 * <p>
 * 如果preSum[R] % k == preSum[L-1] % k，那么必然 preSum[R] - preSum[L-1] 可以被k整除。
 * <p>
 * 利用这个数学性质，我们就不必双重for遍历所有区间了，只需要检查preSum数组中是否存在两个元素 % k 的结果相同，即可说明存在区间之和可以整除k。
 */
public class DigitalGames {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);

        while (sc.hasNextLine()) {
            try {
                int[] tmp = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
                int[] nums = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
                System.out.println(isExist(nums, tmp[1]));
            } catch (Exception e) {
                break;
            }
        }*/

        int[] tmp = Arrays.stream("6 7".split(" ")).mapToInt(Integer::parseInt).toArray();
        int[] nums = Arrays.stream("2 12 6 3 5 5".split(" ")).mapToInt(Integer::parseInt).toArray();
        System.out.println(isExist(nums, tmp[1]));
    }

    /**
     * 前缀和（不进行双指针，所以不用求前缀和数组，只用遍历前缀和即可）
     * @param nums
     * @param m
     * @return
     */
    public static int isExist(int[] nums, int m) {
        HashSet<Integer> remain = new HashSet<>();
        remain.add(0);

        int sum = 0;
        for (int num : nums) {
            sum += num;
            if (remain.contains(sum % m)) {
                return 1;
            } else {
                remain.add(sum % m);
            }
        }

        return 0;
    }
}